The present invention relates generally to semiconductor memory, and more particularly to a tertiary CAM cell.
Many applications require searching information at high speed. In many network devices, such as switches or routers, data packets are transferred based on the contents of embedded address information. Thus, in order to achieve a high data transfer rate, network systems must be able to perform very high speed searches and comparisons. One class of circuits useful for this function is a content addressable memory or CAM. It should be noted that although the following discussion is set within the context of a networked system, there are many other applications which require high speed searching and comparison, and which may also therefore benefit from the present invention. For example, the tag field of a fully associative cache memory also requires high speed searching and may be implemented using a CAM.
It may be useful to compare a CAM against a traditional memory device, such as a random access memory (RAM). To an extent, CAM and RAM device operate conversely. For example, a RAM may be read by presenting it with a read command and an address. The RAM responds by outputting the data stored at the specified address. However, when a CAM is read, it is presented with a data sample, and the CAM returns an match signal indicating whether the data sample is stored in the CAM, and if so, an address within the CAM which contains the data which matched the sample.
Network routers and switches generally employ a matching function, where a portion of a packet, such as an address field, is compared to a list of data entries. The list is often referred to as a database. FIG. 1 is a block diagram of an exemplary CAM device 100, which includes a CAM array 110 for storing the database, a match detection circuit 120 for detecting matches, and optionally a priority encoder 130 for selecting and outputting a matching address in a priority order, when appropriate. The CAM device also includes a controller 140, for controlling the operation of the CAM array 110, match detection logic 120, and priority encoder 130, as well as for interfacing the CAM device 100 to other devices via the data 150a, address 150b, and control 150c lines. Commercially available CAM devices may support, for example, searching a 136-bit wide data sample against a database having up to 16,384 entries. Commercially available CAM devices may be searched at rates up to 100 million searches per second. This ability for CAMs to quickly search relatively wide data words against relatively large databases at high speeds makes them highly useful in applications such as network routing and switching.
There are two types of searches which are of interest, namely a search for the exact match and the partial match search. In the exact match search, an entry stored in the CAM will match the data sample only if the data sample and the entry match bit for bit. In a partial match search, the search may be conducted on only a subset of bits in the word. That is, the CAM entries are permitted to specify a third xe2x80x9cdon""t carexe2x80x9d state in addition to the logical xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d states. When a partial match search is conducted, CAM entries will match a data sample as long as each bit in the entry set at a logical xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d states match the corresponding portion of the data sample.
CAMs having entries which only support the logical xe2x80x9c0xe2x80x9d and logical xe2x80x9c1xe2x80x9d states are known as binary CAMs, and can only support exact match searches. CAMs having entries which also support the use of the xe2x80x9cdon""t carexe2x80x9d state are known as ternary CAMs, and can be used for partial match searches. (These CAMs also support exact match searches when an entry does not contain any xe2x80x9cdon""t carexe2x80x9d states.)
In a ternary CAM, each bit of the database stored in the CAM array 110 must be represented by at least two bits, in order to encode the three required logical states (xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d). Although a number of different technologies can be used to construct the CAM array 110, modern CAM devices use storage elements based upon a static random access memory (SRAM), where data is stored in a flip-flop, or a dynamic random access memory (DRAM), where data is stored in the form of a charge on a capacitor. FIG. 2 is an illustration of a CAM cell 200 based upon DRAM technology.
The cell 200 includes a transistor 202 and a capacitor 203, which are coupled in series between a bit line 201 and a ground potential 206 as illustrated in FIG. 2. A select line 205 is coupled to the gate of the transistor 202. Additionally, the cell 200 inherently includes parasitic capacitance, which is illustrated in FIG. 2 as capacitor 204, coupled between the bit line 201 and ground 206. Data may be stored in the cell 200 by switching transistor 202 on (via line 205) and forcing bit line 201 to either a high or a low state. This causes the capacitor 203 to charge or discharge until the potential at node 207 equals the potential of the bit line. The transistor 202 is then switched off (via line 205) and the potential at node 207 is maintained by the charge stored in capacitor 203.
In order to read data stored in the cell 200, the bit line 201 is precharged to a high level. This ensures that the parasitic capacitance 204 is also charged. The transistor 202 is then switched on (via line 205). If the capacitor 203 is storing a charge so that the potential at node 207 is high, there is no change of potential at node 207 and at the bit line 201. The charge level of the capacitor 203 is also unchanged. However, if the capacitor 203 is storing a charge so that the potential at node 207 is low, charge will flow from the bit line 201 through the transistor 202 and into the capacitor 203. This causes the potential at the bit line 201 to decrease and the potential at node 207 to increase. The charge level of the capacitor 203 also increases. The change in voltage in the bit line 201 and/or at node 207 can be sensed, in order to determine logical stated stored in the capacitor 202.
The CAM cell illustrated in FIG. 2 stores a single bit of data, and is therefore capable of encoding only two states. As previously discussed, ternary CAMs require cells which can encode three states. The 300 circuit illustrated in FIG. 3 is similar to that the circuit 200 illustrated in FIG. 2, but includes two storage elements. This permits the cell 300 to store two bits, which can encode four states, three of which is sufficient to serve the storage requirements of a ternary CAM cell.
One problem associated with dynamic CAM cells 200, 300 is that a read operation may be destructive. In cell 200, for example, when the read operation is performed on a cell in which the capacitor 202 is storing a low level of charge, the flow of charge from the bit line 201 during the read operation alters the charge level of the capacitor 202. Thus, in CAM cells 200, 300, a charge restoration operation is required after each read operation. The requirement for performing a charge restoration operation after each read limits the speed of a CAM device. The charge restoration circuit (not illustrated) also requires additional components and increases power consumption.
FIG. 4 is an illustration of another CAM cell 400. In comparison to the previously described CAM cell 300 (FIG. 3), CAM cell 400 includes two additional transistors 402a, 402b, which are coupled in parallel with the data storage capacitors 203a, 203b, respectively. The gate of transistor 402a is coupled to node 207b while the gate of transistor 402b is coupled to node 207a. These two transistors 402a, 402b provide the circuit 400 a limited form of protection from destructive reads. More specifically, the CAM cell 400 can be read nondestructively only if the capacitors 203a, 203b store opposite charges (i.e., xe2x80x9c0xe2x80x9d+xe2x80x9c1xe2x80x9d or xe2x80x9c1xe2x80x9d+xe2x80x9c0xe2x80x9d). Thus if the CAM cell 400 were used with control circuitry (e.g., controller 140 (FIG. 1)) which only permits storing in CAM cell 400 the two opposite charge states, the CAM cell 400 can be used as a dynamic binary CAM cell not requiring charge restoration after a read. Unfortunately, the CAM cell 400 is unsuitable for use a ternary CAM cell because ternary CAM cells must be able to store at least three states. Accordingly, there is a need and desire for a method and apparatus for an efficient dynamic CAM cell architecture which does not require charge restoration after each read operation.
The present invention is directed to a ternary CAM cell which stores charge in a manner similar to a DRAM cell, but which also can be nondestructively read. That is, a read operation does not have to be followed by a charge restoration operation in order to maintain data integrity. The three required states of a ternary CAM (logical xe2x80x9c0xe2x80x9d, logical xe2x80x9c1xe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d) may be stored using three bits of storage. The use of three bits of storage per CAM cell permits the use of a circuit topology which include three states which can be read nondestructively.